//是否作为DOM Properties 来设置属性 
//  如：el.checked = true  
// 而不是el.setAttribute('checked', true)
function shouldSetAsProps (el, key, value) {
  // 特殊处理， 遇到则补全
  if (key === 'form' && el.tagName === 'INPUT') {
    return false;
  }

  return key in el;
}


// 创建渲染器
function createRenderer (options) {

  //通过options 拿到对应操作的api
  const {
    createElement,
    setElementText,
    insert,
    patchProps,
    createText,
    setText,
    createComment,
    setComment,

  } = options

  // 通过key 复用元素 且移动位置
  /**
 * @param {旧vnode的子节点} oldChildren
 * @param {新vnode的子节点} newChildren
 * @param {容器} container
 */
  function simpleDiff2 (oldChildren, newChildren, container) {
    //新children中 当前子节点 最大索引值
    let lastIndex = 0;
    for (let i = 0; i < newChildren.length; i++) {
      const newChild = newChildren[i];

      // 是否是新元素 没有在旧children中找到
      let find = false;
      for (let j = 0; j < oldChildren.length; j++) {
        const oldChild = oldChildren[j];
        if (newChild.key === oldChild.key) {
          //找到可复用元素
          find = true;

          // 如果当前找到的节点在旧children中的索引小于最大索引值 则需要移动位置
          if (j < lastIndex) {
            // 移动位置
            const prevVnode = newChildren[i - 1];
            // 如果不是第一个元素
            if (prevVnode) {
              // 找到上一个元素的 下一个兄弟元素
              const anchor = prevVnode.el.nextSibling;

              // 插入到anchor前面
              insert(newChild.el, container, anchor);
            }


          } else {
            //如果大于最大索引值 则 更新最大索引值
            lastIndex = j;
          }

          break; // 找到后退出内层循环
        }
      }

      // 如果没有找到 则说明是新元素
      if (!find) {
        // 找到上一个元素的 下一个兄弟元素
        const prevVnode = newChildren[i - 1];
        // 如果不是第一个元素
        let achor;
        if (prevVnode) {
          // 找到上一个元素的 下一个兄弟元素
          anchor = prevVnode.el.nextSibling;

        } else {
          anchor = container.firstChild;
        }

        // 挂载新元素
        patch(null, newChild, container, anchor);
      }
    }

    // 卸载多余的旧元素
    for (let i = 0; i < oldChildren.length; i++) {
      const oldChild = oldChildren[i];
      //看旧元素是否在新的children中
      const find = newChildren.find(child => child.key === oldChild.key);

      //如果不在则卸载
      if (!find) {
        unmount(oldChild);
      }
    }

  }



  //通过长度去更新;没有移动元素逻辑
  /**
   * @param {旧vnode的子节点} oldChildren
   * @param {新vnode的子节点} newChildren
   * @param {容器} container
   */
  function simpleDiff1 (oldChildren, newChildren, container) {
    const oldLen = n1.children.lenght;
    const newLen = n2.children.lenght;
    const minLen = Math.min(oldLen, newLen);


    for (let i = 0; i < minLen.lenght; i++) {
      patch(oldChildren[i], newChildren[i], container)
    }

    if (oldLen > newLen) {
      for (let i = minLen; i < oldLen; i++) {
        unmount(oldChildren[i]);
      }
    } else {
      for (let i = minLen; i < newLen; i++) {
        patch(null, newChildren[i], container);
      }
    }

  }


  // 双端diff 算法
  /**
   * @param {旧vnode} n1
   * @param {新vnode} n2
   * @param {容器} container
   */
  // function patchKeyedChildren (n1, n2, container) {
  //   const oldChildren = n1.children;
  //   const newChildren = n2.children;

  //   // 四个索引 
  //   let oldStartIdx = 0; // 旧children 开始索引
  //   let oldEndIdx = oldChildren.length - 1; // 旧children 结束索引
  //   let newStartIdx = 0; // 新children 开始索引
  //   let newEndIdx = newChildren.length - 1; // 新children 结束索引

  //   // 对应四个节点
  //   let oldStartVnode = oldChildren[oldStartIdx]; // 旧children 开始节点
  //   let oldEndVnode = oldChildren[oldEndIdx]; // 旧children 结束节点
  //   let newStartVnode = newChildren[newStartIdx]; // 新children 开始节点
  //   let newEndVnode = newChildren[newEndIdx]; // 新children 结束节点

  //   // 循环比较
  //   while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  //     // 旧 头部节点 和旧尾部节点不存在 说明也被处理了 ，则 跳过
  //     if (!oldStartVnode.el) {
  //       oldStartVnode = oldChildren[++oldStartIdx];
  //     } else if (!oldEndVnode.el) {
  //       oldEndVnode = oldChildren[--oldEndIdx];
  //     } else if (oldStartVnode.key === newStartVnode.key) {
  //       // 直接打补丁更新 不需要挪动
  //       patch(oldStartVnode, newStartVnode, container);

  //       // 更新 新旧开始节点
  //       oldStartVnode = oldChildren[++oldStartIdx];
  //       newStartVnode = newChildren[++newStartIdx];

  //     } else if (oldEndVnode.key === newEndVnode.key) {
  //       // 直接打补丁更新 不需要挪动
  //       patch(oldEndVnode, newEndVnode, container);

  //       //更新 新旧结束节点
  //       oldEndVnode = oldChildren[--oldEndIdx];
  //       newEndVnode = newChildren[--newEndIdx];

  //     } else if (oldStartVnode.key === newEndVnode.key) {
  //       // 先打补丁后挪动，将旧开始节点挪到 旧结束的下一个兄弟元素的前面
  //       patch(oldStartVnode, newEndVnode, container);

  //       const anchor = oldEndVnode.el.nextSibling;
  //       insert(oldStartVnode.el, container, anchor);

  //       // 更新 旧开始节点 新结束节点
  //       oldStartVnode = oldChildren[++oldStartIdx];
  //       newEndVnode = newChildren[--newEndIdx];

  //     } else if (oldEndVnode.key === newStartVnode.key) {
  //       // 先打补丁后挪东， 将旧结束节点 挪到 旧开始节点的前面
  //       patch(oldEndVnode, newStartVnode, container);

  //       const anchor = oldStartVnode.el;
  //       insert(oldEndVnode.el, container, anchor);

  //       // 更新 旧结束节点 新开始节点
  //       oldEndVnode = oldChildren[--oldEndIdx];
  //       newStartVnode = newChildren[++newStartIdx];
  //     } else {
  //       // 当四个节点都不能匹配时， 则需要在旧节点中查找新开始节点的key
  //       const idxInOld = oldChildren.findIndex(child => child.key === newStartVnode.key);
  //       if (idxInOld > 0) { //找到了就往旧头部节点前插入
  //         const oldVnodeToMove = oldChildren[idxInOld]; // 要移动的旧节点
  //         // 先打补丁
  //         patch(oldVnodeToMove, newStartVnode, container);
  //         // 获取对应锚点
  //         const anchor = oldStartVnode.el;
  //         // 移动元素
  //         insert(oldVnodeToMove.el, container, anchor);
  //         oldChildren[idxInOld] = undefined;
  //       } else { //没有找到说明时新节点， 
  //         patch(null, newStartVnode, container, oldStartVnode.el);
  //       }
  //       newStartVnode = newChildren[++newStartIdx];
  //     }
  //   }

  //   // 看是否有新节点遗漏
  //   if (newStartIdx <= newEndIdx && oldStartIdx > oldEndIdx) {
  //     // 说明新节点有剩余， 则将新节点插入到旧开始节点的前面
  //     for (let i = newStartIdx; i <= newEndIdx; i++) {
  //       patch(null, newChildren[i], container, oldStartVnode.el);
  //     }
  //   } else if (newStartIdx > newEndIdx && oldStartIdx <= oldEndIdx) {// 旧节点有剩余 则卸载
  //     for (let i = oldStartIdx; i <= oldEndIdx; i++) {
  //       unmount(oldChildren[i]);
  //     }

  //   }
  // }

  // 快速diff 算法
  /**
   * @param {旧vnode} n1
   * @param {新vnode} n2
   * @param {容器} container
   */
  function patchKeyedChildren (n1, n2, container) {
    const newChildren = n2.children; // 新children
    const oldChildren = n1.children; // 旧children

    // 处理相同前置节点
    // j 指向新旧子节点的开头
    let j = 0;
    let oldVNode = oldChildren[j]; // 旧children 开头
    let newVNode = newChildren[j]; // 新children 开头
    while (oldVNode.key === newVNode.key) { // 当旧children开头和新children开头的key相同时
      patch(oldVNode, newVNode, container); // 直接打补丁
      j++; // 指针后移
      oldVNode = oldChildren[j]; // 旧children 开头
      newVNode = newChildren[j]; // 新children 开头
    }

    // 处理后置相同节点
    let oldEnd = oldChildren.length - 1; // 旧children 结尾
    let newEnd = newChildren.length - 1; // 新children 结尾
    oldVNode = oldChildren[oldEnd]; // 旧children 结尾
    newVNode = newChildren[newEnd]; // 新children 结尾
    while (oldVNode.key === newVNode.key) { // 当旧children结尾和新children结尾的key相同时
      patch(oldVNode, newVNode, container); // 直接打补丁
      oldEnd--; // 指针前移
      newEnd--; // 指针前移
      oldVNode = oldChildren[oldEnd]; // 旧children 结尾
      newVNode = newChildren[newEnd]; // 新children 结尾
    }

    // 如果旧子节点遍历完，但新子节点 没遍历完
    if (oldEnd < j && newEnd >= j) {
      const achorIndex = newEnd + 1;
      // 锚点元素
      const achor = achorIndex > newChildren.length - 1 ? null : newChildren[achorIndex].el;

      // 如果锚点元素存在 便一直往锚点元素上面插入元素。
      while (j <= newEnd) { // 遍历新子节点
        patch(null, newChildren[j++], container, achor); // 挂载新子节点
      }

    } else if (newEnd < j && oldEnd >= j) { // 如果新子节点遍历完，但旧子节点 没遍历完
      while (j <= oldEnd) { // 遍历旧子节点
        unmount(oldChildren[j++]); // 卸载旧子节点
      }
    } else { //处理非理想情况 
      // 获取剩余未处理的节点数量
      const count = newEnd - j + 1;
      // source 用于记录 对应旧节点的索引
      const source = new Array(count); // 数组长度为 剩余未处理的节点数量
      source.fill(-1); // 填充-1 表示 未处理

      let oldStart = j; // 旧children 开头
      let newStart = j; // 新children 开头

      // 会有性能问题-----------------
      // // oldStart newStart 指向 旧children 和 新children 开头
      // for (let i = oldStart; i <= oldEnd; i++) { // 遍历旧children
      //   const oldVNode = oldChildren[i]; // 旧children 开头
      //   for (let k = newStart; k <= newEnd; k++) { // 遍历新children
      //     const newVNode = newChildren[k]; // 新children 开头
      //     if (oldVNode.key === newVNode.key) { // 当旧children开头和新children开头的key相同时
      //       patch(oldVNode, newVNode, container); // 直接打补丁
      //       source[k - newStart] = i; // 记录旧节点的索引
      //     }
      //   }
      // }

      // 优化版本 ----------------
      // 新增 是否移动标识 和 最大索引值标识（类似简单diff）
      let moved = false; // 是否移动标识
      let pos = 0; // 最大索引值标识
      // 构建索引表
      const keyIndex = {}
      for (let i = newStart; i <= newEnd; i++) { // 遍历新children
        const newVNode = newChildren[i]; // 新children 开头
        keyIndex[newVNode.key] = i; // 记录新节点的索引
      }


      // patched 表示 已更新过的节点数量
      let patched = 0; // 已更新过的节点数量

      // 遍历旧children
      for (let i = oldStart; i <= oldEnd; i++) { // 遍历旧children
        const oldVNode = oldChildren[i]; // 旧children 开头

        // 如果已更新过的节点数量 小于等于 剩余未处理的节点数量 则继续
        if (patched <= count) {

          const k = keyIndex[oldVNode.key]; // 通过索引表找到对应key的新节点的索引
          if (k !== undefined) { // 如果找到了
            patch(oldVNode, newChildren[k], container); // 直接打补丁
            // k - newStart 是为了获取 新节点 在 source 数组中的正确索引
            source[k - newStart] = i; // 记录旧节点的索引

            if (k < pos) {
              // 如果新节点的索引小于最大索引值标识 说明需要移动
              moved = true; // 设置移动标识为 true
            } else {
              // 如果新节点的索引大于最大索引值标识 说明不需要移动
              pos = k; // 更新最大索引值标识为 当前新节点的索引
            }

          } else {
            unmount(oldVNode); // 如果没有找到 则卸载旧节点
          }
        } else {
          unmount(oldVNode); // 如果已更新过的节点数量 大于 剩余未处理的节点数量 则卸载旧节点
        }

      }

      if (moved) {
        // 计算最长递增子序列
        const seq = getSequence(source); // 计算最长递增子序列 
        const s = seq.length - 1; // 最长递增子序列的长度
        let i = count - 1;

        for (i; i >= 0; i--) {
          if (source[i] === -1) {
            // 说明是   新增的节点
            const pos = newStart + i;
            const newVNode = newChildren[pos]; // 新children 开头
            const nextPos = pos + 1;
            const achor = nextPos > newChildren.lenght ? null : newChildren[nextPos].el; // 新children 开头
            patch(null, newVNode, container, achor); // 插入到下一个兄弟元素的前面

          }else if(i!== seq[s]){
            // 说明是 移动的节点
            const pos = newStart + i; // 新children 开头
            const newVNode = newChildren[pos]; // 新children 开头
            const nextPos = pos + 1; // 新children 开头
            const achor = nextPos > newChildren.lenght? null : newChildren[nextPos].el; // 新children 开头
            patch(null, newVNode, container, achor); // 插入到下一个兄弟元素的前面
          }else {
            s--;
          }
        }

      }


    }
  }


  /**
   * @param {旧vnode} n1
   * @param {新vnode} n2
   * @param {容器} container
   */
  function patchChildren (n1, n2, container) {
    //如果新节点是字符串
    if (typeof n2.children === 'string') {
      // 如果旧节点是数组  则需要先卸载
      if (Array.isArray(n1.children)) {
        n1.children.forEach(child => {
          unmount(child);
        })
      }

      // 无论旧节点是 字符串或null直接设置文本覆盖即可，无需额外处理
      setElementText(container, n2.children)
    } else if (Array.isArray(n2.children)) {// 如果新节点有多个子节点


      // 旧节点的子节点是否为数组
      if (Array.isArray(n1.children)) {
        //双端diff算法处理。
        patchKeyedChildren(n1, n2, container);


      } else {
        // 无论是旧节点的子节点是 字符串还是null,先清空容器 再遍历打补丁
        setElementText(container, '');
        n2.children.forEach(child => {
          patch(null, child, container);
        })
      }
    } else {
      if (Array.isArray(n1.children)) {
        n1.children.forEach(child => {
          unmount(child);
        })
      } else {
        setElementText(container, '');
      }
    }
  }

  /**
    * @param {旧vnode} n1
    * @param {新vnode} n2 
    * 
    */
  function patchElement (n1, n2) {
    // 复用旧的元素
    const el = n2.el = n1.el;
    const oldProps = n1.props;
    const newProps = n2.props;

    //1. 更新props 
    for (const key in newProps) {
      if (newProps[key] !== oldProps[key]) {
        patchProps(el, key, oldProps[key], newProps[key])
      }
    }
    for (const key in oldProps) {
      if (!(key in newProps)) {
        // 如果新的props 中不存在这个属性  则删除这个属性
        patchProps(el, key, oldProps[key], null)
      }
    }

    // 2. 更新children
    pathChildren(n1, n2, el)
  }



  // 卸载元素
  function unmount (vnode) {
    if (vnode.type === Fragment) {
      vnode.children.forEach(child => {
        unmount(child);
      })
      return;
    }

    const parente = vnodel.el.parentNode;
    if (parente) {
      parente.removeChild(vnode.el)
    }
  }


  // 挂载元素
  function mountElement (vnode, container, anchor) {
    // 创建type类型元素
    const el = vnode.el = createElement(vnode.type);

    // 处理子节点 如果是string  表示元素有文本节点
    if (typeof vnode.children === 'string') {
      // 设置文本节点
      setElementText(el, vnode.children);
    } else if (Array.isArray(vnode.children)) {
      vnode.children.forEach(child => {
        //因为目前只是 挂载阶段 所以 旧vnode 传null即可
        patch(null, child, el)
      });
    }

    // 如果存在属性
    if (vnode.props) {
      for (const key in vnode.props) {
        // 调用setAttribute 方法设置数据
        const value = vnode.props[key]

        // 调用patchProps 方法设置属性
        patchProps(el, key, null, value);
      }
    }


    // 将元素添加到容器中
    insert(el, container, anchor);
  }

  //文本节点的标识
  const Text = Symbol();
  //注释节点的标识
  const Comment = Symbol();
  //  片段节点的标识
  const Fragment = Symbol();

  /**
   * n1 @param {*} 旧vnode
   * n2 @param {*} 新vnode
   * container @param {*} 容器
   *  在这里编写渲染逻辑
   */
  function patch (n1, n2, container, anchor) {

    // 区分新旧节点是否同一类型
    if (n1 && n1.type !== n2.type) {
      // 不是同一类型  就直接卸载旧的 
      unmount(n1);
      n1 = null;
    }


    const { type } = n2

    // 如果是字符串则表明是普通标签
    if (typeof type === 'string') {
      // 如果旧vnode 不存在 就表示挂载
      if (!n1) {
        // 挂载
        mountElement(n2, container, anchor)
      } else {
        // 打补丁  暂时省略
      }
    } else if (type === Text) {
      // 如果是文本节点
      if (!n1) {
        const el = n2.el = createText(n2.children);
        insert(el, container);
      } else {
        const el = n2.el = n1.el;
        if (n2.children !== n1.children) {
          setText(el, n2.children);
        }
      }

    } else if (type === Comment) {
      // 如果是注释节点
      if (!n1) {
        const el = n2.el = createComment(n2.children);
        insert(el, container);
      } else {
        const el = n2.el = n1.el;
        if (n2.children !== n1.children) {
          setComment(el, n2.children);
        }
      }
    } else if (type === Fragment) {
      // 如果是片段节点
      if (!n1) {
        // 如果就节点不存在，则直接遍历挂载fragment的子节点
        n2.children.forEach(child => {
          patch(null, child, container)
        })
      } else {//如果是旧节点
        // 就只需要比较Fragment上的子节点即可，
        // 因为Fragment 没有真实的DOM  所以 直接复用旧节点的子节点
        patchChildren(n1, n2, container)
      }
    } else if (typeof type === 'object') {
      // 如果是对象 则它描述是组件

    } else if (typeof type === 'xxx') {
      // 其他类型 vnode  特殊处理
    }

  }



  function render (vnode, container) {
    if (vnode) {
      // 新 节点存在， 就将旧vnode 一起传给patch 函数 进行打补丁
      // container._vnode 表示旧vnode
      patch(container._vnode, vnode, container)
    } else {
      if (container._vnode) {
        // 只有旧vnode 存在，  没有新vnode   就是卸载操作
        // container.innerHTML = '';
        unmount(container._vnode);
      }
    }


    // 存vnode 作为下一个的旧vnode
    container._vnode = vnode;
  }

  // 服务端渲染内容时讲解
  function hydrate (vnode, container) {
  }

  return {
    render,
    hydrate
  }
}



const vnode = {
  type: 'div',
  props: {
    id: 'foo',
    class: normalizeClass({
      name1: '1',
    }),
    onClick: () => {
      alert('11');
    },
    onContentmenu: () => {
      alert('22');
    }
  },
  textContent: 'hello'
}


const renderer = createRenderer({
  createElement (tag) {
    return document.createElement(tag);
  },
  setElementText (el, text) {
    el.textContent = text;
  },
  insert (el, parent, anchor = null) {
    parent.insertBefore(el, anchor);
  },
  createText (text) {
    return document.createTextNode(text);
  },
  setText (el, text) {
    el.nodeValue = text;
  },

  creatComment (text) {
    return document.createComment(text);
  },
  setComment (el, text) {
    el.nodeValue = text;
  },

  patchProps (el, key, prevValue, nextValue) {
    if (/^on/.test(key)) {
      // 定义 el._vei 为一个对象，存在事件名称到事件处理函数的映射
      const invokers = el._vei || (el._vei = {});

      //获取为该元素伪造的事件处理函数 invoker
      let invoker = invokers[key];
      // 获取事件名称  如：onClick  => click
      const name = key.slice(2).toLowerCase();

      if (nextValue) {
        if (!invoker) {
          // 第一次绑定事件
          // 为元素创建一个伪造的事件处理函数 invoker
          //vei  vue event invoker
          // 将事件处理函数映射到对应的key下，避免覆盖。
          invoker = el._vei[key] = (e) => {

            // e.timeStamp 事件发生的时间
            // 如果事件发生的时间小于事件处理函数绑定的时间 则直接return
            //--------- 此处是为了屏蔽绑定事件晚于事件发生事件的事件处理函数的 执行-----
            if (e.timeStamp < invoker.attached) return;

            // 当伪造事件执行的时候  会执行真正的事件处理函数 
            // 如果是个数组 则遍历执行  否则 直接执行
            if (Array.isArray(invoker.value)) {
              invoker.value.forEach(fn => fn(e))
            } else {
              invoker.value(e)
            }
          }

          //将真正的事件处理函数赋值给 invoker.value
          invoker.value = nextValue;

          // 记录时间绑定的时间
          invoker.attached = performance.now();

          // 新绑定事件
          el.addEventListener(name, invoker);
        } else {
          // 如果invoker 存在 则表示 更新 事件
          // 只需要更新 invoker.value 即可
          invoker.value = nextValue;
        }
      } else if (invoker) {
        //新事件不存在 且之前绑定的事件存在 则 移除事件
        el.removeEventListener(name, invoker.value);
      }

    } else if (key === 'class') {
      el.className = nextValue || '';
    } else if (shouldSetAsProps(el, key, nextValue)) {
      const type = typeof el[key]
      if (type === 'boolean' && nextValue === '') {
        el[key] = true;
      } else {
        el[key] = nextValue;
      }
    } else {
      el.setAttribute(key, nextValue);
    }
  }
})

renderer.render(vnode, document.querySelector('#app'));